package sa.Master.common.Functions;

import java.util.AbstractList;

public class BinarySearch {

    public static int unsignedAverage(int a, int b) {
        return (a&b)+((a^b)>>1);
    }

    /**
     * Get a specific item's index in a sorted list.
     *
     * Note:
     * 1. Although all kinds of list implemented {@code AbstractList} containing an {@code Comparable}
     *    is legal for this function, we strongly recommend the List be an {@code RandomAccess}.
     *    Otherwise the time complexity would be higher than expected.
     * 2. If there are multiple objects equal to value, then return the smallest index
     *
     * @param list The list in which to search.
     * @param value The value to search.
     * @param <T> implements Comparable.
     * @return A non-negative integer which is the index if found, -1 if not found.
     */
    public static <T extends Comparable<? super T> > int indexOf(AbstractList<T> list, final T value, boolean ascending) {

        int mid, l=0, r=list.size()-1;
        while (l<=r) {
            mid = unsignedAverage(l, r);
            int compareResult = list.get(mid).compareTo(value);

            if ((ascending && compareResult<0) || (!ascending && compareResult>0)) {
                l = mid+1;
            } else {
                r = mid-1;
            }
        }
        if (list.get(l).compareTo(value)==0) {
            return l;
        } else {
            return -1;
        }

    }
}
